package common

/*TODO
层序遍历
前中后序遍历
建立二叉树
建立二叉搜索树

递归/迭代方式

时间复杂度:O(N)
空间复杂度:O(N)
*/

// 二叉树层序遍历
func LevelOrder(root *TreeNode) []*TreeNode {
	if root == nil {
		return nil
	}
	ret := make([]*TreeNode, 0)
	//存储每一层的节点（不包含空节点）
	level := []*TreeNode{root}
	for len(level) != 0 {
		pos := len(level)
		for _, node := range level {
			if node != nil {
				level = append(level, node.Left, node.Right)
			}
			ret = append(ret, node)
		}
		level = level[pos:]
	}
	return ret
}

//递归解法，调用方法：LevelOrder(root, ret, 1)
func LevelOrder1(root *TreeNode, ret [][]int, index int) [][]int {
	if root == nil {
		return ret
	}
	//遍历到更深的一层，再ret中添加一个slice
	if len(ret) < index {
		ret = append(ret, []int{})
	}

	//把当前层的节点的Val存入ret中
	ret[index-1] = append(ret[index-1], root.Val)
	LevelOrder1(root.Left, ret, index+1)
	LevelOrder1(root.Right, ret, index+1)
}
